A packet switching network has switching points or nodes (commonly referred to as switches or routers) for transmissions of data among senders and receivers connected to the network. The switching performed by these switching points is in fact the action of passing on packets of data received by a switching point or node to a further node in the network. Such switching actions are the means by which communication data is moved through the packet switching network.
Each switch or router may comprise what is commonly referred to as a “control point” coupled to one or more processors commonly referred to as network processors. Network processor(s) may be configured to process packets of data. The control point may be a processor configured to manage the overall operation of the switch or router. For example, the control point may be configured to initialize network processor(s), download boot or diagnostic code, install operational code on the network processor(s) as well as transmit frames, i.e., packets of data, to network processor(s), to perform particular operations on a tree, e.g., insert leaf, update leaf, read leaf, delete leaf, as discussed in further detail below.
These frames or packets of data transmitted to the network processor(s) from the control point may comprise commands to perform a particular operation on a tree, e.g., insert leaf, update leaf, read leaf, delete leaf, as discussed in further detail below. A tree may refer to a conceptual or graphical representation of data organized in a tree structure. A leaf may refer to the end node of a tree storing data, e.g., next hop address. These frames may further comprise a tree identifier, a key such as a 32-bit binary number used to search the tree and leaf data (if any). The network processor may use a portion of the bits of the key, e.g., 16 most significant bits, to index into an entry in a table commonly referred to as a direct table. The direct table may comprise entries storing either a leaf or an address of a first node of a tree structure. Each node in a tree may commonly be referred to as a Pattern Search Control Block (PSCB). If the entry indexed into the direct table is a PSCB, then the remaining bits of the key, e.g., 16 least significant bits, that are not used for indexing into the direct table, may be used to traverse the tree to locate the leaf. That is, the remaining bits of the key, e.g., 16 least significant bits, may be used to locate the leaf. Upon locating the leaf, the network processor executes the received command, e.g., read the leaf, delete the leaf, update the leaf using the received leaf data, insert the leaf data using the received leaf data.
As stated above, a tree may refer to a conceptual or graphical representation of data organized in a tree structure. The tree structure may comprise a starting point commonly referred to as a root that is connected to other points in the tree structure commonly referred to as nodes. Each of these nodes may be connected to other nodes thereby forming “branches.” As stated above, the node at the end of each branch may be referred to as a leaf.
Various tree operations or functions may be performed on the tree structure. For example, a function referred to as the “insert leaf” function may refer to inserting data at a particular leaf in a particular tree structure. The function referred to as the “update leaf” function may refer to updating the data associated with a particular leaf. The function referred to as the “read leaf” function may refer to reading the data associated with a particular leaf. The function referred to as the “delete leaf” function may refer to deleting a leaf from a particular tree structure.
Formerly, all tree operations such as the ones described above were executed serially on a single thread. However, performing tree operations serially on a single thread was slow and inefficient so tree operations started to be performed on multiple threads. However, when performing tree operations using multiple threads, memory corruption may occur. The tree operations described above may involve inserting and/or deleting nodes of the tree structure thereby modifying the tree structure. If multiple tree operations occur in a substantially concurrent manner, then inserts and/or deletes may occur in a substantially concurrent manner in the same region of the tree thereby resulting in inconsistent node updates.
It would therefore be desirable to eliminate memory corruption when performing multi-threaded tree functions, e.g., insert leaf, update leaf, read leaf, delete leaf.